In mathematics, a rational monoid is a

monoid In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0. Monoids ...

, an algebraic structure, for which each element can be represented in a "normal form" that can be computed by a finite transducer: multiplication in such a monoid is "easy", in the sense that it can be described by a

rational function In mathematics, a rational function is any function that can be defined by a rational fraction, which is an algebraic fraction such that both the numerator and the denominator are polynomials. The coefficients of the polynomials need not be rat ...

Definition

Consider a monoid ''M''. Consider a pair (''A'',''L'') where ''A'' is a finite subset of ''M'' that generates ''M'' as a monoid, and ''L'' is a language on ''A'' (that is, a subset of the set of all strings ''A''^∗). Let ''φ'' be the map from the

free monoid In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero eleme ...

''A''^∗ to ''M'' given by evaluating a string as a product in ''M''. We say that ''L'' is a ''rational cross-section'' if ''φ'' induces a bijection between ''L'' and ''M''. We say that (''A'',''L'') is a ''rational structure'' for ''M'' if in addition the

kernel Kernel may refer to: Computing * Kernel (operating system), the central component of most operating systems * Kernel (image processing), a matrix used for image convolution * Compute kernel, in GPGPU programming * Kernel method, in machine learnin ...

of ''φ'', viewed as a subset of the product monoid ''A''^∗×''A''^∗ is a

rational set In computer science, more precisely in automata theory, a rational set of a monoid is an element of the minimal class of subsets of this monoid that contains all finite subsets and is closed under union, product and Kleene star. Rational sets are us ...

. A quasi-rational monoid is one for which ''L'' is a rational relation: a rational monoid is one for which there is also a

cross-section of ''L''. Since ''L'' is a subset of a free monoid,

Kleene's theorem In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to ...

holds and a rational function is just one that can be instantiated by a finite state transducer.

Examples

* A finite monoid is rational. * A

group A group is a number of persons or things that are located, gathered, or classed together. Groups of people * Cultural group, a group whose members share the same cultural identity * Ethnic group, a group whose members share the same ethnic ide ...

is a rational monoid if and only if it is finite. * A finitely generated free monoid is rational. * The monoid M4 generated by the set subject to relations in which ''e'' is the identity, 0 is an

absorbing element In mathematics, an absorbing element (or annihilating element) is a special type of element of a set with respect to a binary operation on that set. The result of combining an absorbing element with any element of the set is the absorbing element i ...

, each of ''a'' and ''b'' commutes with each of ''x'' and ''y'' and ''ax'' = ''bx'', ''ay'' = ''by'' = ''bby'', ''xx'' = ''xy'' = ''yx'' = ''yy'' = 0 is rational but not automatic. * The Fibonacci monoid, the quotient of the free monoid on two generators ^∗ by the congruence ''aab'' = ''bba''.

Green's relations

The

Green's relations In mathematics, Green's relations are five equivalence relations that characterise the elements of a semigroup in terms of the principal ideals they generate. The relations are named for James Alexander Green, who introduced them in a paper of 1951. ...

for a rational monoid satisfy ''D'' = ''J''.Sakarovitch (1987)

Properties

Kleene's theorem holds for rational monoids: that is, a subset is a recognisable set if and only if it is a rational set. A rational monoid is not necessarily automatic, and vice versa. However, a rational monoid is asynchronously automatic and

hyperbolic Hyperbolic is an adjective describing something that resembles or pertains to a hyperbola (a curve), to hyperbole (an overstatement or exaggeration), or to hyperbolic geometry. The following phenomena are described as ''hyperbolic'' because they ...

. A rational monoid is a regulator monoid and a quasi-rational monoid: each of these implies that it is a Kleene monoid, that is, a monoid in which Kleene's theorem holds.

References

* * * * * {{cite journal , title=Easy multiplications I. The realm of Kleene's theorem , first=Jacques , last=Sakarovitch , journal=Information and Computation , volume=74, number=3 , date=September 1987 , pages=173–197 , doi=10.1016/0890-5401(87)90020-4 , zbl=0642.20043 , doi-access=free Algebraic structures Semigroup theory